package C021;

import java.util.Arrays;

/**
 * ClassName: MergeSort
 * Package: C021
 * Description:
 *
 * @Author BCXJ
 * @Create 2024/12/6 17:21
 * @Version 1.0
 * @Since 1.0
 */
public class MergeSort {
    public static void main(String[] args) {
        int n = 10000;
        int length = 200;
        int size = 100;
        for (int i = 0; i < n; i++) {
            int[] arr1 = generateRandomArr(length, size);
            int[] arr2 = Arrays.copyOf(arr1, arr1.length);
            int[] arr3 = Arrays.copyOf(arr1, arr1.length);
            Arrays.sort(arr1);
            mergeSort(arr2, 0, arr1.length - 1);
            mergeSortNonRecur(arr3);
            if(!Arrays.equals(arr1, arr2) || !Arrays.equals(arr1, arr3)) {
                System.out.println("error !!!!");
                System.out.println(Arrays.toString(arr1));
                System.out.println(Arrays.toString(arr2));
                System.out.println(Arrays.toString(arr3));
                return;
            }
        }
        System.out.println("success !!!!");
    }

    public static int[] generateRandomArr(int n, int size) {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = (int) (Math.random() * size);
        }
        return arr;
    }

    public static void mergeSort(int[] arr, int l, int r) {
        if(r == l) {
            return;
        }
        int m = r + ((l - r) >> 2);
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        merge(arr, l, r, m);
    }

    private static void merge(int[] arr, int l, int r, int m) {
        int[] help = new int[r - l + 1];
        int index = 0;
        int i = l, j = m +1;
        while(i <= m && j <= r) {
            if(arr[i] <= arr[j]) {
                help[index++] = arr[i++];
            }else {
                help[index++] = arr[j++];
            }
        }
        while(i <= m) {
            help[index++] = arr[i++];
        }
        while(j <= r) {
            help[index++] = arr[j++];
        }
        for(int k = 0; k < help.length; k++) {
            arr[l + k] = help[k];
        }
    }


    /**
     * 归并排序 - 非递归实现
     * @param arr
     */
    public static void mergeSortNonRecur(int[] arr) {
        int step = 1; // 2 的倍数递增
        for (int l, r, m = 0; step < arr.length; step <<= 1) {
            l = 0;
            while (l < arr.length) {
                m = l + step - 1;
                if(m + 1 >= arr.length) {
                    break;
                }
                r = Math.min(l + (step << 1) - 1, arr.length - 1);
                merge(arr, l, r, m);
                l = r + 1;
            }
        }
    }

}
